package com.coder.algorithm.offer_2;

/**
 * 最长不含重复字符的字符串
 *
 * @author yuhushuan
 * @date 2020/6/27 22:46
 */
public class _48_1_LongestSubstringWithoutDup {
    private static int longestSubstring(String str) {
        if (str == null) {
            return 0;
        }

        int curLength = 0;
        int maxLength = 0;

        // 利用数组保存字符上次出现的位置
        int[] position = new int[26];
        for (int i = 0; i < 26; ++i) {
            position[i] = -1;
        }

        for (int i = 0; i < str.length(); ++i) {
            int curChar = str.charAt(i);
            int preIndex = position[curChar - 'a'];

            // 当前字符距离上次字符出现的距离
            int distance = i - preIndex;
            // distance 大于 上一字符最长子字符串，证明此子字符串内不包含当前字符
            if (preIndex < 0 || distance > curLength) {
                curLength++;
            } else {// 上一个字符最长子字符串内包含和当前字符
                curLength = distance;
            }
            if (maxLength < curLength) {
                maxLength = curLength;
            }
            position[curChar - 'a'] = i;
        }
        return maxLength;
    }

    public static void main(String[] args) {
        // 功能测试
        // 多个字符的字符串
        print("arabcacfr");
        print("rfcacbara");
        // 只有一个字符
        print("b");
        // 所有字符都相同
        print("bbbbbbb");

        // 特殊输入测试
        print(null);
        print("");
    }

    private static void print(String str) {
        System.out.println("字符串：" + str);
        System.out.println("最长子字符串长度为：" + longestSubstring(str));
        System.out.println();
    }
}
